package com.leetcode.www;
/**
 * Creared with IntelliJ IDEA.
 * Description:给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
 *
 * 你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
 *
 * 返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * User:yxd
 * Date:2022-02-26
 * Time:20:34
 */
public class Normal121 {
    public static void main(String[] args) {
        int[] array = {7,1,5,3,6,4};
        System.out.println(maxProfit(array));
    }
    public static int maxProfit(int[] prices) {
        if(prices == null || prices.length == 0){
            return 0;
        }
        //状态定义：F(i) 第i天卖出所获得的最大利润
        //状态转移方程： F(i) = Math.max(F(i - 1),prices[i] - Math.min(前面的所有数))
        //初始值F(0)= 0第一天买入第一条卖出
        int[] dp = new int[prices.length];
        dp[0] = 0;
        int min_val = prices[0];
        int max_val = dp[0];
        for(int i = 1;i < prices.length;i ++){
            if(min_val > prices[i]){
                min_val = prices[i];//记录前面的最小值
            }
            dp[i] = Math.max(dp[i - 1],prices[i] - min_val);
            if(max_val < dp[i]){
                max_val = dp[i];
            }
        }
        return max_val;
    }
}
